//请判断一个链表是否为回文链表。 
//
// 示例 1: 
//
// 输入: 1->2
//输出: false 
//
// 示例 2: 
//
// 输入: 1->2->2->1
//输出: true
// 
//
// 进阶： 
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 链表 双指针

package leetcode.editor.cn;

import java.util.ArrayList;

public class PalindromeLinkedList {
    public static void main(String[] args) {
        Solution solution = new PalindromeLinkedList().new Solution();
//        ListNode listNode = ListNodeUtil.constructList(new int[]{1, 0,1});
        ListNode listNode = ListNodeUtil.constructList(new int[]{1, 2, 2, 1});
        System.out.println(solution.isPalindrome(listNode));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isPalindrome(ListNode head) {
            //找到中点位置，从这里开始反转后半段链表
            //再次找到中点位置，中点与head开始进行对比，中途有不相同的返回false，否则最后返回true
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode slow = dummy;//遍历结束时slow指向的是mid的前一个
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            ListNode head2 = reverse(slow.next);
            slow.next = null;
            while (head != null && head2 != null) {
                if (head.val != head2.val) {
                    return false;
                } else {
                    head = head.next;
                    head2 = head2.next;
                }
            }
            return true;
        }


        /**
         * 反转链表
         *
         * @param head
         * @return
         */
        private ListNode reverse(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode pre = dummy;
            ListNode cur = pre.next;
            /**
             * prev  cur   next   next
             */
            while (cur.next != null) {
                ListNode nextNext = cur.next.next;

                cur.next.next = cur;
                cur.next = nextNext;
                pre.next = cur;

                cur = cur.next;

            }
            return pre.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}